package hwTwo1;

import java.util.ArrayList;

public class ShellSort {
    public static void sort(Comparable[] a) {
        int n = a.length;

        // **1. 预先计算递增序列并存储到数组中**
        ArrayList<Integer> increments = new ArrayList<>();
        int h = 1;
        while (h < n) {
            increments.add(h);
            h = 3 * h + 1; // Knuth 增量序列
        }

        // 转换为数组，便于从后向前遍历
        int[] incrementArray = new int[increments.size()];
        for (int i = 0; i < increments.size(); i++) {
            incrementArray[i] = increments.get(increments.size() - 1 - i); // 逆序存储
        }

        // **2. 使用预先计算的递增序列进行希尔排序**
        for (int inc : incrementArray) { // 遍历每个增量值
            for (int i = inc; i < n; i++) {
                Comparable temp = a[i];
                int j = i;
                // 插入排序逻辑：对当前增量 inc 进行排序
                while (j >= inc && less(temp, a[j - inc])) {
                    a[j] = a[j - inc];
                    j -= inc;
                }
                a[j] = temp;
            }
        }
    }

    // 辅助方法：判断 v 是否小于 w
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // 辅助方法：打印数组
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    // 测试代码
    public static void main(String[] args) {
        String[] a = {"E", "A", "S", "Y", "S", "H", "E", "L", "L", "S", "O", "R", "T", "Q", "U", "E", "S", "T", "I", "O", "N"};
        sort(a);
        show(a);
    }
}